import sun.reflect.generics.tree.Tree;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;

public class Leet102 {
    /**
     * 给你一个二叉树，请你返回其按 层序遍历 得到的节点值。 （即逐层地，从左到右访问所有节点）。
     * 示例：
     * 二叉树：[3,9,20,null,null,15,7],
     *     3
     *    / \
     *   9  20
     *     /  \
     *    15   7
     * 返回其层序遍历结果：
     * [
     *   [3],
     *   [9,20],
     *   [15,7]
     * ]
     */
     public class TreeNode {
         int val;
      TreeNode left;
      TreeNode right;
      TreeNode(int x) { val = x; }
    }
    public List<List<Integer>> levelOrder(TreeNode root) {


        List<List<Integer>> lists = new ArrayList<List<Integer>>();
        if (root==null){
             return lists;
         }
        LinkedList<TreeNode> linkedList=new LinkedList();
        linkedList.add(root);

         while (linkedList.size()>0) {
            ArrayList<Integer> arrayList = new ArrayList<>();
            int n=linkedList.size();

            for (int i=0;i<n;i++) {
                TreeNode treeNode = linkedList.removeFirst();
                arrayList.add(treeNode.val);

                if (treeNode.left!=null) {
                    linkedList.add(treeNode.left);
                }
                if (treeNode.right!=null){
                    linkedList.add(treeNode.right);
                }
            }
            lists.add(arrayList);
        }

         return lists;
    }
}
